import java.io.BufferedReader;
import java.io.InputStreamReader;

class BSTNode {
		int data;
		BSTNode left;
		BSTNode right;
		public BSTNode(int d,BSTNode n, BSTNode n1){
			this.data = d;
			this.left = n;
			this.right = n1;
			}
	}

	public class BinarySearchTree {

		public BSTNode root = null;
		
		
		public   void insert(int data){
			BSTNode temp_root = root;
		    if (temp_root==null) {
		        temp_root = new BSTNode(data, null, null);
		        root = temp_root;
		    }else{
		        internalInsert(temp_root, data);
		    }
		}
		 
		private static void internalInsert(BSTNode node, int data){
		    // Not the same value twice
		    if (data == node.data) {
		        return;
		    }
		 
		    if (data < node.data) {
		        if (node.left == null) {
		            node.left = new BSTNode(data, null, null);
		        }else{
		            internalInsert(node.left, data);
		        }
		    }else{
		        if (node.right == null) {
		            node.right = new BSTNode(data, null, null);
		        }else{
		            internalInsert(node.right, data);
		        }	
		    }
		}
		public void printInOrder(BSTNode root){
			if (root.left != null) printInOrder(root.left);
			System.out.println(root.data+" -> ");
			if (root.right != null) printInOrder(root.right);
		}
		
		public void printPreOrder(BSTNode root){
			System.out.println(root.data+" -> ");
			if (root.left != null) printPreOrder(root.left);
			if (root.right != null) printPreOrder(root.right);
		}
		
		public void printPostOrder(BSTNode root){
			if (root.left != null) printPostOrder(root.left);
			if (root.right != null) printPostOrder(root.right);
			System.out.println(root.data+" -> ");
		}
		
	
		public static void main(String[] args) {
			// TODO Auto-generated method stub
			BinarySearchTree l = new BinarySearchTree();
			l.insert(4);
			l.insert(8);
			l.insert(7);
			l.insert(1);
			l.insert(2);
			l.insert(3);
			l.insert(9);
		    System.out.println("Inorder traversal of the tree");
			l.printInOrder(l.root);
		    System.out.println("Preorder traversal of the tree");
		    l.printPreOrder(l.root);
		    System.out.println("Postorder traversal of the tree");
		    l.printPostOrder(l.root);
		    System.out.println("Enter the element to be searched in the BST");
		    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		    int find_node = 4;
		    try {
		    	find_node = Integer.parseInt(br.readLine());	
		    }catch (Exception e){
		    	System.out.println(e.getMessage());
		    }
		    l.searchBST(l.root,find_node);
		    
		    System.out.println("Enter two nodes one by one to find its least common ancestor");
		    int node1=1,node2=4;
		    try {
		    	node1 = Integer.parseInt(br.readLine());
		    	node2 = Integer.parseInt(br.readLine());
		    }catch (Exception e){
		    	System.out.println(e.getMessage());
		    }
		    System.out.println(l.leastCommonAncestor(l.root,node1,node2));
		    
		}

		private int leastCommonAncestor(BSTNode root, int n1, int n2) {
			/* If we have reached a leaf node then LCA doesn't exist
		     If root->data is equal to any of the inputs then input is
		     not valid. For example 20, 22 in the given figure http://geeksforgeeks.org/?p=1029*/
			int return_value =0 ;
			if (root ==null ||root.data == n1 || root.data ==n2) return -1;
			if((root.right!=null )&&(root.right.data == n1 ||root.right.data == n2 )) return root.data;
			if((root.left!=null )&&(root.left.data == n1 ||root.left.data == n2 )) 	return root.data;
						
			if(root.data > n1 && root.data < n2) return root.data;
			
			if(root.data > n1 && root.data > n2) return_value = leastCommonAncestor(root.left, n1, n2);
			if(root.data < n1 && root.data < n2) return_value = leastCommonAncestor(root.right, n1, n2);
			
			return return_value;
						
		}

		private void searchBST(BSTNode node, int data) {
			if(data == node.data) {
				System.out.println("Node found");
			}
			else if (data < node.data) {
			        if (node.left != null) {
			           searchBST(node.left, data);
			        }else {
						System.out.println("Node not found");
					}
			    }
			else if (data > node.data){
			        if (node.right != null) {
			        	searchBST(node.right, data);
			        }	else {
						System.out.println("Node not found");
					}
			    }
			
		}

	}
